/**
 * 
 */
package zhoujian.oj.leetcode;

import static org.hamcrest.Matchers.is;
import static org.junit.Assert.assertThat;

import java.util.Arrays;

import org.junit.Test;

import com.algs4.stdlib.In;
import com.algs4.stdlib.Stopwatch;

/**
 * @author hyper
 * @email zjkermit@gmail.com
 * @date Dec 30, 2013
 * @version 1.0
 * @description 
 * 		Given an array S of n integers, find three integers in S such that the 
 * 		sum is closest to a given number, target. Return the sum of the three 
 * 		integers. You may assume that each input would have exactly one 
 * 		solution.
 * 
 * 		For example, given array S = {-1 2 1 -4}, and target = 1.
 * 		The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
 */
public class ThreeSumClosest {

	public int threeSumClosest(int[] num, int target) {
		Arrays.sort(num);
		int res = num[0] + num[1] + num[2];
		int aRes = Math.abs(res - target);
		int origin;
		int left;
		int right;
		int sum;
		int t;
		for (int i = 0; i < num.length - 2;) {
			origin = num[i];
			left = i + 1;
			right = num.length - 1;
			while (left < right) {
				sum = origin + num[left] + num[right];
				t = Math.abs(sum - target);
				if (sum == target) {
					return sum;
				} else if (t < aRes) {
					res = sum;
					aRes = t;
				} else if (sum > target) {
					right--;
				} else {
					left++;
				}
			}
			while (++i < num.length && num[i] == origin);
		}
		
		return res;
	}
	
	public int threeSumClosest2(int[] num, int target) {  
        // Start typing your Java solution below  
        // DO NOT write main() function  
        if (num.length < 3)  
            return 0;  
        Arrays.sort(num);  
        int origin, left, right, res = 0, sum, distance = Integer.MAX_VALUE, cur_dis;  
        for (int i = 0; i < num.length - 2;) {  
            origin = num[i];  
            left = i + 1;  
            right = num.length - 1;  
            while (left < right) {  
                sum = origin + num[left] + num[right];  
                cur_dis = Math.abs(origin + num[left] + num[right] - target);  
                if(cur_dis < distance){  
                    distance = cur_dis;  
                    res = sum;  
                }  
                if (sum == target) {  
                    return res;  
                } else if (sum >= target) {  
                    --right;  
                } else {  
                    ++left;  
                }  
            }  
            while (++i < num.length && num[i] == origin);  
        }  
        return res;  
    }  
	
	@Test
	public void testThreeSumClosest() {
		int[] num = new int[]{ 0, 2, 1, -3 };
		assertThat(threeSumClosest(num, 1),  is(0));
		assertThat(threeSumClosest2(num, 1),  is(0));
	}
	
	@Test
	public void testTime() {
		In in = new In("src/main/resources/data/16Kints.txt");
		int[] num = in.readAllInts();
		int[] num2 = Arrays.copyOf(num, num.length);
		int target = 100;
		
		Stopwatch s = new Stopwatch();
		threeSumClosest(num, target);
		System.out.println("threeSumClosest : " + s.elapsedTime());
		in.close();
		
		s = new Stopwatch();
		threeSumClosest2(num2, target);
		System.out.println("threeSumClosest2 : " + s.elapsedTime());
		in.close();
	}
}
